package medium;

import java.util.*;

/**
 * 1600. 王位继承顺序
 * 创建时间：2024-04-07 21:57
 * 地址：https://leetcode.cn/problems/throne-inheritance/description
 */
public class 王位继承顺序_1600 {
    static class ThroneInheritance {
        Map<String, List<String>> map;
        Set<String> dead;
        String king;
        public ThroneInheritance(String kingName) {
            map = new HashMap<>();
            dead = new HashSet<>();
            king = kingName;
        }

        public void birth(String parentName, String childName) {
            List<String> children = map.getOrDefault(parentName, new ArrayList<>());
            children.add(childName);
            map.put(parentName, children);
        }

        public void death(String name) {
            dead.add(name);
        }

        public List<String> getInheritanceOrder() {
            List<String> ans = new ArrayList<>();
            preOrder(ans, king);
            return ans;
        }

        private void preOrder(List<String> ans, String name) {
            if (!dead.contains(name)) {
                ans.add(name);
            }
            List<String> children = map.getOrDefault(name, new ArrayList<>());
            for (String child : children) {
                preOrder(ans, child);
            }
        }
    }

    public static void main(String[] args) {

    }
}
